#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int n1 = nums1.size();
        int n2 = nums2.size();
        if (n1 == 0)
        {
            return (nums2[n2 / 2] + nums2[(n2 - 1) / 2]) / 2.0;
        }
        if (n2 == 0)
        {
            return (nums1[n1 / 2] + nums1[(n1 - 1) / 2]) / 2.0;
        }
        if (n1 > n2)
            return findMedianSortedArrays(nums2, nums1);
        int half = (n1 + n2 + 1) / 2;
        int split1 = -1;
        int range = n1 / 2;
        while (true)
        {
            int split2 = half - split1 - 2;
            // check
            if (split1 > 0 && split2 + 1 < n2 && nums1[split1] > nums2[split2 + 1])
            {
                // split --
                split1 -= range;
                range = max(range / 2, 1);
            }
            else if (split2 > 0 && split1 + 1 < n1 && nums1[split1 + 1] < nums2[split2])
            {
                // split ++
                split1 += range;
                range = max(range / 2, 1);
            }
            else
            {
                if ((n1 + n2) % 2)
                    if (split1 < 0)
                        return nums2[split2];
                    else if (split2 < 0)
                        return nums1[split1];
                    else
                        return max(nums1[split1], nums2[split2]);
                else
                {
                    int v1;
                    if (split1 < 0)
                        v1 = nums2[split2];
                    else if (split2 < 0)
                        v1 = nums1[split1];
                    else
                        v1 = max(nums1[split1], nums2[split2]);
                    int v2;
                    if (split1 + 1 > n1 - 1)
                        v2 = nums2[split2 + 1];
                    else if (split2 + 1 > n2 - 1)
                        v2 = nums1[split1 + 1];
                    else
                        v2 = min(nums1[split1 + 1], nums2[split2 + 1]);
                    return (v1 + v2) / 2.0;
                }
            }
        }
    }
};

int main()
{
    cout << "Code4" << endl;
    Solution s;
    vector<int> nums1 = {0, 0, 0, 0, 0};
    vector<int> nums2 = {-1, 0, 0, 0, 0, 0, 1};
    cout << s.findMedianSortedArrays(nums1, nums2) << endl;
    return 0;
}